//回文串分割: https://www.nowcoder.com/practice/1025ffc2939547e39e8a38a955de1dd3?tpId=46&tqId=29048&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
class Solution {
public:
    int minCut(string s) {
        if (s.empty())
            return 0;
        int len = s.size();
        vector<int> cut;
        // F(i)初始化
        // F(0）=
        // -1，必要项，如果没有这一项，对于重叠字符串“aaaaa”会产生错误的结果
        for (int i = 0; i < 1 + len; ++i) {
            cut.push_back(i - 1);
        }
        for (int i = 1; i < 1 + len; ++i) {
            for (int j = 0; j < i; ++j) {
                // F(i) = min{F(i), 1 + F(j)}, where j<i && j+1到i是回文串
                // 从最长串判断，如果从第j+1到i为回文字符串
                // 则再加一次分割，从1到j，j+1到i的字符就全部分成了回文字符串
                if (isPalindrome(s, j, i - 1)) {
                    cut[i] = min(cut[i], 1 + cut[j]);
                }
            }
        }
        return cut[len];
    }
    // 判断是否回文串
    bool isPalindrome(string s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
};